package com.example.programmerinterview;

/**
 * 面试题 08.05. 递归乘法
 * 递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
 * <p>
 * 示例1:
 * <p>
 * 输入：A = 1, B = 10
 * 输出：10
 * 示例2:
 * <p>
 * 输入：A = 3, B = 4
 * 输出：12
 * <p>
 * 思路：快速幂拆分
 * 如 13 * 12 = 13 * (8 + 4) = 13 * 8 + 13 * 4 = (13 << 3) + (13 << 2)
 * <<1为乘2  >>1为除2
 * 本题将入参的两个数取大max，小min值，将其理解为有min个最大值
 * 所以如果是
 */
public class Multiply {
    public static int multiply(int A, int B) {
        int min = Math.min(A, B);
        int max = Math.max(A, B);
        int ans = 0;
        for (int i = 0; min != 0; i++) {
            if ((min & 1) == 1) {//奇数
                max <<= i;
                ans += max;
            }
            min >>= 1;
        }
        return ans;
    }

    /**
     * 记住此方法，与n次方的快速幂思路相同 求A*B
     */
    public static int multiply2(int A, int B) {
        int res = 0;
        long b = B;
        while (b > 0) {
            if ((b % 2) != 0) res += A; //if ((b & 1) == 1) res *= x;
            A += A; //2个a-快速幂
            b /= 2; //b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Multiply.multiply2(4, 3);
    }

}

